package demo;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: jiume
 * Date: 2024-12-22
 * Time: 10:08
 */
public class Demo {
}


class 两两交换链表中的结点 {
    // 不讲武德的解法：直接交换结点的值
    // public ListNode swapPairs(ListNode head) {
    //     if (head == null || head.next == null) {
    //         return head;
    //     }
    //     ListNode prev = head, cur = head.next;
    //     while (cur != null) { // cur是要交换的结点
    //         int tmp = prev.val;
    //         prev.val = cur.val;
    //         cur.val = tmp;
    //         prev = prev.next.next;
    //         cur = cur.next == null ? null : cur.next.next;
    //     }
    //     return head;
    // }

    // 迭代的写法
    // public ListNode swapPairs(ListNode head) {
    //     if (head == null || head.next == null) {
    //         return head;
    //     }
    //     ListNode newHead = new ListNode(-1, head); // 哨兵位节点
    //     // 修改cur后面的两个结点
    //     ListNode node1 = head, node2 = head.next, cur = newHead;
    //     while (node2 != null) { // node2为null时，均满足上述两种情况
    //         // 下面的修改不能变换
    //         node1.next = node2.next;
    //         node2.next = node1;

    //         cur.next = node2;
    //         // 修改指针指向
    //         cur = node1;
    //         node1 = cur.next;
    //         node2 = node1 == null ? null : node1.next;
    //     }
    //     return newHead.next;
    // }

    // 递归的写法
    // 赋予swapPairs函数一个功能：给你一个指针，将这个指针所指向的链表节点两两交换
    public ListNode swapPairs(ListNode head) {
        // 1、递归的截止条件
        if (head == null || head.next == null) {
            return head;
        }
        // 2、解决一个子问题：交换两个结点
        ListNode cur = swapPairs(head.next.next);
        ListNode node = head.next;
        head.next = cur;
        node.next = head;
        return node;
    }
}


class Solution {
    // 暴力枚举(错误解法)
    // public double myPow(double x, int n) {
    //     if (n == 0 || x == 1) {
    //         return 1;
    //     }
    //     if (n == Integer.MAX_VALUE || n == Integer.MIN_VALUE) {
    //         return 0;
    //     }
    //     double sum = 1;
    //     if (n < 0) {
    //         n = -n;
    //         x = 1 / x;
    //         for (int i = 0; i < n; i++) {
    //             sum *= x;
    //         }
    //     } else if (n > 0) {
    //         for (int i = 0; i < n; i++) {
    //             sum *= x;
    //         }
    //     }
    //     return sum;
    // }

    // 快速幂+递归
    public double myPow(double x, int n) {
        // 当n<0时，是无法求出最终结果的
        return n < 0 ? pow(1/x, -n) : pow(x, n);
    }

    // 赋予pow函数的意义：求出x的n次方
    private double pow(double x, int n) {
        // 1、递归的截止条件
        if (n == 1) {
            return x;
        }
        if (n == 0) { // 避免出现n=0的情况
            return 1;
        }
        // 求x的n次方，就先求x的n/2次方
        double tmp = pow(x, n/2);
        // 求出x的n/2次方后，就可以通过两者相乘的方式求出最终结果
        return n % 2 == 0 ? tmp*tmp : tmp*tmp*x;
    }
}


class ListNode {
    int val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}